import java.util.HashMap;
import java.util.Map;

/**
 * 205. 同构字符串
 * https://leetcode-cn.com/problems/isomorphic-strings/
 */
public class Solutions_205 {
    public static void main(String[] args) {
//        String s = "egg", t = "add";  // output: true
//        String s = "foo", t = "bar";  // output: false
//        String s = "paper", t = "title";  // output: true
        String s = "ab", t = "aa";  // output: false

        boolean result = isIsomorphic(s, t);
        System.out.println(result);
    }

    /**
     * 解法三：哈希表优化（2ms）
     */
    public static boolean isIsomorphic(String s, String t) {
        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();
        // 若 s 能够替换为 t，t 可以替换为 s，则 s 和 t 都能够互换
        return canMap(sarr, tarr) && canMap(tarr, sarr);
    }

    public static boolean canMap(char[] sarr, char[] tarr) {
        // 不使用 26 长度存储，否则无法判断值为 0 的情况
        int[] map = new int[128];
        for (int i = 0; i < sarr.length; i++) {
            int m = sarr[i], n = tarr[i];
            if (map[m] == 0) {
                // 未映射过，直接进行映射
                map[m] = n;
            } else {
                // 已映射过，但是 n 字符与之前映射的字符不同
                if (n != map[m]) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 解法二：字符串查找（10ms）
     */
    public static boolean isIsomorphic3(String s, String t) {
        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();

        for (int i = 0; i < sarr.length; i++) {
            int m = s.indexOf(sarr[i]);
            int n = t.indexOf(tarr[i]);
            if (m != n) {
                // 若映射合法，那么双方查找到的索引则一定相等
                return false;
            }
        }
        return true;
    }

    /**
     * 解法一：哈希表（9ms）
     */
    public static boolean isIsomorphic2(String s, String t) {
        // key：字符，value：映射的字符
        Map<Character, Character> map = new HashMap<>();
        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();
        for (int i = 0; i < sarr.length; i++) {
            char m = sarr[i];
            char n = tarr[i];
            if (map.containsKey(m)) {
                // 已映射过，如果本次映射字符与之前的不同，那么 return false
                if (n != map.get(m)) {
                    return false;
                }
            } else {
                // 未映射过，但字符 n 已经被其他字符映射过，那么 return false
                if (map.containsValue(n)) {
                    return false;
                }
                // 可以进行映射
                map.put(m, n);
            }
        }
        return true;
    }
}
